package 剑指Offer;

public class Offer49_丑数 {
    public int nthUglyNumber(int n) {
        //三指针， 用到了那个，那个就加一

        int a = 0;
        int b = 0;
        int c = 0;
// dp[i] 代表第 i + 1 个丑数；
        int[] dp = new int[n];
        //base case
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            int aa = dp[a] * 2;
            int bb = dp[b] * 3;
            int cc = dp[c] * 5;

            dp[i] = Math.min(Math.min(aa, bb), cc);
            if (dp[i] == aa) {
                a++;// 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            }
            if (dp[i] == bb) {
                b++;// 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
            }
            if (dp[i] == cc) {
                c++;// 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
            }
        }
        return dp[n - 1];
    }
}
